# """
# This is ArrayReader's API interface.
# You should not implement it, or speculate about its implementation
# """
class ArrayReader:
    def __init__(self, lst):
        self.lst = lst

    def get(self, index: int) -> int:
        return self.lst[index] if 0 <= index < len(self.lst) else 2147483647


class Solution:
    def search(self, reader, target):
        left, right = 0, 20000
        while left < right:
            mid = (left + right) // 2
            v = reader.get(mid)
            if v > target:
                right = mid
            elif v < target:
                left = mid + 1
            else:
                return mid
        return left if reader.get(left) == target else -1


if __name__ == "__main__":
    print(Solution().search(reader=ArrayReader([-1, 0, 3, 5, 9, 12]), target=9))  # 4
    print(Solution().search(reader=ArrayReader([-1, 0, 3, 5, 9, 12]), target=2))  # -1
